// 面试题 02.01. 移除重复节点

// 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

#include <stdio.h>

struct ListNode
{
    int val;
    struct ListNode *next;
};

// 双重循环
//  struct ListNode* removeDuplicateNodes(struct ListNode* head)
//  {
//      if(!head || !head->next)
//          return head;

//     struct ListNode *p = head;

//     while(p != NULL)
//     {
//         struct ListNode *m = p;

//         while(m->next != NULL)
//         {

//         if(m->next->val == p->val)
//         {
//             m->next = m->next->next;
//         }
//         else
//             m = m->next;
//         }

//         p = p->next;
//     }

//     return head;
// }

// 双指针法
struct ListNode *removeDuplicateNodes(struct ListNode *head)
{
    if (!head || !head->next)
        return head;

    int arr[20001] = {0};
    struct ListNode *p = head;
    struct ListNode *q = head->next;

    arr[head->val] = 1;

    while (q != NULL)
    {
        // 若q的值不存在，使其为1
        if (arr[q->val] == 0)
        {
            arr[q->val] = 1;
            p = q;
            q = q->next;
        }
        // 若q的值存在，去除该q节点
        else
        {
            p->next = q->next;
            q = p->next;
        }
    }

    return head;
}